#include "StdAfx.h"
#include "GrahamImplementation.h"

/*	
* GrahamImplementation.cpp 
* Created on: 2010-10-25 
* Author: codesmuggler 
* Website: http://codesmuggler.com 
*/ 

// return true if an angle between
// point A, central point and line
// parallel to the axis OX passing through central point
// is smaller than point B angle

class GrahamAngleComparator 
{
	public:  GrahamAngleComparator(CvPoint c) : central(c) {};
	bool operator() (CvPoint a, CvPoint b) 
	{    
		return getAngle(a) < getAngle(b);  
	}  
	double getAngle(CvPoint a) 
	{    
		CvPoint w = cvPoint(a.x - central.x, a.y - central.y);    
		return acos(w.x/(sqrt((double)(w.x*w.x+w.y*w.y))));    
		// w.x*w.x+w.y*w.y shouldn't be 0 ;)  
	}
	private:  CvPoint central;
}; 

// returns true if the point located
// if point A is located below point B
// (or if y-coords are equals - check x-coords
// for the leftmost point)

class GrahamMinComparator 
{
	public:  
		bool operator()(CvPoint a, CvPoint b) 
		{    
			if(a.y < b.y) 
			{      
				return true;    
			} 
			else if(a.y == b.y) 
			{      
				if(a.x < b.x) 
				{        
					return true;
				}
			}
			return false;
		}
} minComparator; 

double GrahamImplementation::counter_clock_wise(CvPoint p3) 
{  
	CvPoint p1 = cstack.top();  
	cstack.pop();  
	CvPoint p2 = cstack.top();
	double res = (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
 	cstack.push(p1);  
	return res;
} 

CvPoint* GrahamImplementation::compute(vector<CvPoint> points, int& nVertex, std::vector<CvPoint> &result) 
{  
	vector<CvPoint>::iterator it = min_element(points.begin(),    points.end(), minComparator);  
	swap(*it,*points.begin());  
	sort(points.begin()+1, points.end(),    GrahamAngleComparator(points[0]));  
	// Clear stack
	while (!cstack.empty())
	{
		cstack.pop();
	}	
	// first 3 points  
	for(int i=0; i < 3; ++i) 
	{    
		cstack.push(points[i]);  
	}

	for(unsigned int i=3; i < points.size(); ++i)
	{
		
		while(counter_clock_wise(points[i]) > 0) 
		{      
			cstack.pop();
		}
		cstack.push(points[i]);
	}

	CvPoint* retval;
	retval = new CvPoint [cstack.size()];
	nVertex = (int) cstack.size();
	int count = 0;
	while (!cstack.empty())
	{
		retval[count] = cstack.top();
		result.push_back(cstack.top());
		cstack.pop();
		count++;
	}
	return retval;
}

